#!/usr/bin/python
# -*-coding:utf-8 -*-

def quick_sort_standard(array, low, high):
    if low<high:
        key_index = partion(array, low, high)
        quick_sort_standard(array, low, key_index)
        quick_sort_standard(array, key_index+1, high)


def partion(array, low, high):
    key = array[low]
    while low<high:
        while low<high and array[high] >= key:
            high -= 1
        if low < high:
            array[low] = array[high]
        
        while low<high and array[low]<key:
            low+=1
        if low < high:
            array[high] = array[low]

    array[low] = key

    return low

if __name__ == '__main__':
    array2 = [9,3,2,1,4,6,7,0,5]

    print(array2)
    quick_sort_standard(array2, 0, len(array2)-1)
    print(array2)